#!/usr/bin/env python
# _*_coding:utf-8_*_

"""
优先级队列
arr = []
heapq.heapify(arr)
1. 计算优先级队列长度: 优先级队列无法直接用 len(pq) 算长度，只能用 len(arr) 来计算长度
2. 每次 heappop , arr 中元素就会减少一个;每次 heappush,arr 中元素就会增加一个;
heappop

@Time : 2022/2/14 17:45
@Author: RunAtWorld
@File: priority_queue.py
"""
import heapq

def test_pq_simple():
    arr = [4, 3, 2, 5, 8, 9, 10, 1]
    import heapq
    heapq.heapify(arr)
    print(heapq.heappop(arr))
    heapq.heappush(arr, 13)
    while arr:
        print(heapq.heappop(arr), end=',')

def test_pq():
    arr = [(5, 'a'), (4, 'b'), (8, 'c'), (9, 'e'), (1, 'f')]
    heapq.heapify(arr)
    heapq.heappush(arr, (7, 'd'))
    for i in range(5):
        print(heapq.heappop(arr))
    heapq.heappush(arr, (2, 'x'))
    print(heapq.heappop(arr))


def test_pq_class():
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

    n5 = ListNode(0)
    n4 = ListNode(2, n5)
    n3 = ListNode(3, n4)
    n2 = ListNode(4, n3)
    n1 = ListNode(5, n2)
    arr = []
    head = n1
    while head:
        arr.append((head.val, head, 'x'))
        head = head.next
    heapq.heapify(arr)
    for i in range(5):
        val, node, memo = heapq.heappop(arr)
        print(val, node, memo)
    heapq.heappush(arr, (2, 'x', 'a'))
    print(heapq.heappop(arr))


def test_pq_dic():
    # nlargest(n, iterable, key=None)
    # nsmallest(n, iterable, key=None)
    # n:查找个数 iterable:可迭代对象 key：同sorted

    list1 = [1, 6, 4, 3, 9, 5]
    list2 = ['12', 'a6', '4', 'c34', 'b9', '5']
    list3 = [
        {'name': 'jim', 'age': 23, 'price': 500},
        {'name': 'mase', 'age': 23, 'price': 600},
        {'name': 'tom', 'age': 25, 'price': 2000},
        {'name': 'alice', 'age': 22, 'price': 300},
        {'name': 'rose', 'age': 21, 'price': 2400},
    ]

    from operator import itemgetter
    import heapq

    print(heapq.nlargest(len(list1), list1))
    print(heapq.nlargest(3, list2))
    print(heapq.nlargest(len(list3), list3, key=itemgetter('age', 'price')))
    """
    [9, 6, 5, 4, 3, 1]
    ['c34', 'b9', 'a6']
    [{'name': 'tom', 'age': 25, 'price': 2000}, 
    {'name': 'mase', 'age': 23, 'price': 600}, 
    {'name': 'jim', 'age': 23, 'price': 500}, 
    {'name': 'alice', 'age': 22, 'price': 300}, 
    {'name': 'rose', 'age': 21, 'price': 2400}]
    """
    # 以上代码输出结果同sorted

    print(heapq.nsmallest(len(list1), list1))
    print(heapq.nsmallest(len(list2), list2))
    print(heapq.nsmallest(len(list3), list3, key=itemgetter('age', 'price')))
    # 结果是降序
    """
    [1, 3, 4, 5, 6, 9]
    ['12', '4', '5', 'a6', 'b9', 'c34']
    [{'name': 'rose', 'age': 21, 'price': 2400}, 
    {'name': 'alice', 'age': 22, 'price': 300},
     {'name': 'jim', 'age': 23, 'price': 500}, 
     {'name': 'mase', 'age': 23, 'price': 600},
     {'name': 'tom', 'age': 25, 'price': 2000}]
    """

    # 从以下形式的dict中取value最大的2个key - value的value
    dict_num_num = {0: 0.07374631268436578, 1: 0.16307692307692306, 2: 0.11455108359133127, 3: 0.06748466257668712,
                    4: 0.08383233532934131, 5: 0.11081794195250659, 6: 0.04261463063367381, 7: 0.0,
                    8: 0.2742382271468144, 9: 0.06963788300835655, 10: 0.0, 11: 0.0, 12: 0.0, 13: 0.0}
    max_n = heapq.nlargest(2, dict_num_num.items(), key=lambda x: x[1])
    print(max_n)


if __name__ == '__main__':
    # test_pq_simple()
    # test_pq()
    # test_pq_class()
    test_pq_dic()
